ࡱ> @B?7 bjbjUU "67|7|lttt8,Bpp$ R-    < \ W ^t 0Bj j HYPERLINK "Wavelets.doc"Previous lectureHYPERLINK "..\\Review\\Modulation.doc"Next Lecture HYPERLINK "..\\320Syllabus.doc" SyllabusFractals in Graphics Fractal A geometrically complex object, the complexity of which arises from the repetition of form over some range of scale. Fractal dimension In Euclidean geometry, dimensions are integers: 0 for a point, 1 for a line, 2 for a plane, 3 for space. Here the fractal dimension can be non-integer. For example, 2.3 is a plane plus a 0.3 fractal increment. It gives a measure of how densely the fractal fills the part of the next higher dimension. A fractal dimension of 2.1 has little outside a plane, while a dimension of 2.9 would fill most of space. The shape becomes more convoluted as the fractal increment increases. The underlying shape that generates the fractal is called the basis function. It is often something like a noisy sine wave that produces a lump. These lumps are added in at various positions and at various scales to produce a fractal. Frequency The size of the lumps. Amplitude Lump height. Lacunarity The size of the gap between successive frequencies. Usually set to 2, which corresponds to an octave (doubling of frequency) in music. Number of octaves The number of different scale sizes that get used. The fractal dimension relates the scaling in frequency to the scaling in amplitude. Fractal self-similarity only occurs over a limited range of scales. These are called the lower crossover scale and the upper crossover scale. For example, the Himalayas and the runway at JFK have approximately the same fractal dimension (roughness); they differ in their crossover scales. Fractals are useful in generating visual complexity in synthetic images. They can generate realistic mountains, clouds and water. Non-self-similar textures such as hair and grass are better generated by other methods. Fractals to Characterize Textures An important task in image processing is to segment separate regions. This can be done by finding the edges between regions, by identifying regions by color or gray scale, or by identifying textures in the regions. Here are examples of two images whose regions contain different textures: One method to characterize textures is to try to estimate the fractal dimension. Consider an image I, broken up into N non-overlapping copies of a basic shape, each one scaled by a factor of r from the original. The fractal dimension D is I = NrD We might know D for an image that we create, but natural scenes with texture will not have exact replicas of the basic shape. It is possible to estimate D. Once we do that, we can represent a natural texture very compactly. There are claims of achieving 1000:1 compression using fractals. Fractal compression is asymmetric: it takes a lot of computation to find the fractal characteristics of an image and compress it. Fractal decompression is fast. One way to estimate the fractal dimension is to compute the Hurst coefficient. The definition of the fractal dimension can be rewritten as D = - log N / log r If we plot log(N) against log(r) we should get a straight line whose slope is approximately D. [Parker, pp. 172-174] The images produced with the fractal estimate are:  Fixed Point Transformation A function f has a fixed point x0 if f(x0) = x0. If the function is a line, f(x) = a x + b, and a ( 1, then there is a fixed point with equation x0 = b / (1 - a). If we know this equation, then instead of transmitting x0, we could transmit a and b. The receiver could then recover x0. The receiver does not need to solve the equation. It can reconstruct x0 by using an iterative process: x0(n+1) = a x0(n) + b Suppose we have an image I and a function for which f(I) = I. If it is cheaper to transmit the function f than the image I, we can do so and achieve compression. Certain natural-looking objects can be obtained as the fixed points of a certain type of function. Can we solve the inverse problem? Given an image I, find a function f for which I is a fixed point. An approach to doing this is to partition the image into regions and try to find fixed point transformations for each region. Let fk be the transformation for a region k and pcr be the value of a pixel at column c and row r within this region. We will assume that we can get the transformation by shuffling and rearranging pixels within the block: fk (pcr) = h(ak pcr + Dk) where we need to find values for a scaling ak, a translation Dk and an isometry function h. The isometry can be Rotation by 0, 90, 180 or -90 degrees. Reflection about the horizontal, vertical or either diagonal axis. In general, this will be computationally intensive, but there are some shortcuts that can make it feasible. Fractal compression tends to perform about the same as the DCT in JPEG. Fractals are a new approach and additional research may lead to significant improvements. HYPERLINK "Wavelets.doc"Previous lectureHYPERLINK "..\\Review\\Modulation.doc"Next Lecture HYPERLINK "..\\320Syllabus.doc" Syllabus CS 320  PAGE 3 Dec 4, 00 +,-.TUVbcde^l ) * ; < XY =>?@6H* j U jU6H* jU jU6j_UjU0JjU jUL-d() igeeeee$$Ifl\:,"04 la$If 2K' ( | {  i$$Ifl0,"LL04 la$If %"$a$i$$Ifl0,"LL04 la$If@DGJKQRST   VWXxyz{|  [\^_`bfghijln^`OJQJ6]6H*H*H*6H* j6Zx2[6KS$If & F$a$`b  CDEQRSTuvw0JmHnHu0J j0JUj Uj? U0Jj U jU6]OJQJ6H*#omkmmm$$Ifl\:,"04 la 1h/ =!"#$%DyK F Wavelets.docWavelets.docDyK FReview\Modulation.docDyK F320Syllabus.docDdrV  c 2AT1.pngb#)< 0 󢻣En)< 0 󢻣PNG  IHDRnpIDATxѮ! D[rʊ(34b}g‚Vlt.^Px="o-OJ:+%ڳVKt's%ÁVdpBbWFcq䶏w@7M&y SarcPnw Yv87;ʷMfM)7ޱq(ﴵÎFzpÓE0ʎ޽F{gyͤEgGEۻu@Zzg+~wyYwVn>*9AUz7΋> l5Ob])/Ơ˼3칹wQ^gޑtb1}B{wL;}@}^Nw"doq7,R93R-{¼X](1er,۱p{web{T..#HsoIENDB`Dd66V  c 2AT2.pngbTYju9!zqT0n(Yju9!zqTPNG  IHDRjjqJKIDATx 0 as}3ӖI!+^,OP[?;ߟqqBóUBíx* OVKr+Z+VTS)Z#܊pɶ\nEEޫL([ѪqQݽ"lnE܊j&WZ.V˭hU\Tw[*h3 Ҵ ܊Vᢊ{U~U4Gr+Z|[#jIմj5ѵQuMIENDB`DdnprZ  c 6AT1fr.pngbmT7 "LSI8LInAT7 "LSI8LPNG  IHDRnpIDATxn DI՞y{oRRF2y.@.sr7[.@,=W)YOκ\ܿnye^n{)GD?:rdf*QnHsMr 3!)5T@Լ 0nzARZܚ$;妚 J)ֹufun#K9-km&%ņ Q֙a'#qP5#Av"9ˍ5Fݏ;*=gquKGwpnIuszgU={|B$*My&58J.[89>|1\7U3W3^j5Txrޛoy/wy__R)rG{gRzoi7,Ԋ*B*ph,@, Header  !, @, Footer  !&)@!& Page Number6-d() 2K'(|{  % " x2[u OP_`0000000000000000000000000000000000000000000000000000 0 00000000000@0 0 @` +-Ubd`zXXXXXX !TKU []_bhjkn Tyler FolsomZC:\WINNT\Profiles\TFolsom\Application Data\Microsoft\Word\AutoRecovery save of Fractal.asd Tyler Folsom.C:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom0C:\windows\TEMP\AutoRecovery save of Fractal.asdTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.docTyler C. Folsom.D:\DigiPen\CS320\Lectures\Wavelets\Fractal.doc Tyler Folsom.C:\DigiPen\CS320\Lectures\Wavelets\Fractal.docz  hh^h`OJQJo(z-d{ _`@PPX"GPP@{(qq`@``0@UnknownGz Times New Roman5Symbol3& z Arial"qhjK&""L& t#$0d42Q|Fractal  A geometrically complex object, the complexity of which arises from the repletion of form over some range of scale Tyler Folsom Tyler FolsomOh+'0 ,DP\p    }Fractal A geometrically complex object, the complexity of which arises from the repletion of form over some range of scalerrac Tyler Folsomeomyleyle Normal.dotm Tyler Folsomeom10eMicrosoft Word 9.0i@@NߺX@B^t՜.+,D՜.+, hp  a DigiPen Institute of Technology#4 }Fractal A geometrically complex object, the complexity of which arises from the repletion of form over some range of scale Title 8@ _PID_HLINKSAD< ...\320Syllabus.doc6h ..\Review\Modulation.docX  Wavelets.doc ...\320Syllabus.doc6h..\Review\Modulation.docX Wavelets.doc4& T1.png4% T2.pngRT T1fr.pngRW T2fr.png  !"#%&'()*+,-.012345689:;<=>ARoot Entry Fb!^CData 1Table$jWordDocument"6SummaryInformation(/DocumentSummaryInformation87CompObjjObjectPoolb!^b!^  FMicrosoft Word Document MSWordDocWord.Document.89q